/**
 * 你将会获得一系列视频片段，这些片段来自于一项持续时长为 time 秒的体育赛事。这些片段可能有所重叠，也可能长度不一。
 *
 * 使用数组 clips 描述所有的视频片段，其中 clips[i] = [starti, endi] 表示：某个视频片段开始于 starti 并于 endi 结束。
 *
 * 甚至可以对这些片段自由地再剪辑：
 *
 * 例如，片段 [0, 7] 可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。
 * 我们需要将这些片段进行再剪辑，并将剪辑后的内容拼接成覆盖整个运动过程的片段（[0, time]）。返回所需片段的最小数目，如果无法完成该任务，则返回 -1 。
 *
 *https://leetcode.cn/problems/video-stitching/description/
 * 题解：https://labuladong.gitee.io/algo/3/29/101/
 */
class VideoStitching {
    public int videoStitching(int[][] clips, int time) {
        Arrays.sort(clips, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0]==o2[0]) {
                    return o2[1]-o1[1];
                }
                return o1[0]-o2[0];
            }
        });
        int i=0;
        int curEnd=0;
        int nextEnd=0;
        int len=clips.length;
        int res=0;
        while(i<len&&clips[i][0]<=curEnd) {
            while(i<len&&clips[i][0]<=curEnd) {
                nextEnd=Math.max(nextEnd,clips[i][1]);
                i++;
            }
            res++;
            curEnd=nextEnd;
            if(curEnd>=time) {
                return res;
            }
        }
        return -1;
    }
}